package com.wang.violentrecursion;

/**
 * @Author: along
 * @Create: 2021/5/5
 * @Description:斐波拉契数（返回斐波拉契数列的第N项）
 */
public class Demo08_Fib {
    //暴力递归 存在重复计算计算过程
    public static int fib1(int N) {
        if(N == 0 || N == 1) {//base case
            return 1;
        }
        return fib1(N - 1) + fib1(N - 2);//递推公式
    }
    //备忘录模式（空间换时间）
    public static int fib2(int[] memo,int N){
        if(N == 0 || N == 1) {//base case
            return 1;
        }
        if(memo[N] != 0) {//备忘录中存在计算过的值课直接返回，不必重复计算
            return memo[N];
        }
        memo[N] = fib2(memo,N-1) + fib2(memo,N-2);//每次计算的值都会存入备忘录供以后计算使用
        return memo[N];
    }
    //动态规划
    public static int dpWays( int N) {
        if(N == 0 || N == 1) {//base case
            return 1;
        }
        int a = 0, b = 0, c = 1;
        for (int i = 1; i <= N ; ++i) {
            a = b;
            b = c;
            c = a + b;//滚动数组思想
        }
        return c;
    }
    public static void main(String[] args) {
        int N = 10;
        int[] memo = new int[N + 1];
        System.out.println(fib1(N));
        System.out.println(fib2(memo,N));
        System.out.println(dpWays(N));
    }
}
